{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Decoded String at Index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: decodeAtIndex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #索引处的解码字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个编码字符串 <code>S</code>。请你找出<em> </em><strong>解码字符串</strong> 并将其写入磁带。解码时，从编码字符串中<strong> 每次读取一个字符 </strong>，并采取以下步骤：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果所读的字符是字母，则将该字母写在磁带上。</li>\n",
    "\t<li>如果所读的字符是数字（例如 <code>d</code>），则整个当前磁带总共会被重复写&nbsp;<code>d-1</code> 次。</li>\n",
    "</ul>\n",
    "\n",
    "<p>现在，对于给定的编码字符串 <code>S</code> 和索引 <code>K</code>，查找并返回解码字符串中的第&nbsp;<code>K</code>&nbsp;个字母。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>S = &quot;leet2code3&quot;, K = 10\n",
    "<strong>输出：</strong>&quot;o&quot;\n",
    "<strong>解释：</strong>\n",
    "解码后的字符串为 &quot;leetleetcodeleetleetcodeleetleetcode&quot;。\n",
    "字符串中的第 10 个字母是 &quot;o&quot;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>S = &quot;ha22&quot;, K = 5\n",
    "<strong>输出：</strong>&quot;h&quot;\n",
    "<strong>解释：</strong>\n",
    "解码后的字符串为 &quot;hahahaha&quot;。第 5 个字母是 &quot;h&quot;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>S = &quot;a2345678999999999999999&quot;, K = 1\n",
    "<strong>输出：</strong>&quot;a&quot;\n",
    "<strong>解释：</strong>\n",
    "解码后的字符串为 &quot;a&quot; 重复 8301530446056247680 次。第 1 个字母是 &quot;a&quot;。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= S.length &lt;= 100</code></li>\n",
    "\t<li><code>S</code>&nbsp;只包含小写字母与数字 <code>2</code> 到 <code>9</code> 。</li>\n",
    "\t<li><code>S</code>&nbsp;以字母开头。</li>\n",
    "\t<li><code>1 &lt;= K &lt;= 10^9</code></li>\n",
    "\t<li>题目保证 <code>K</code> 小于或等于解码字符串的长度。</li>\n",
    "\t<li>解码后的字符串保证少于&nbsp;<code>2^63</code>&nbsp;个字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [decoded-string-at-index](https://leetcode.cn/problems/decoded-string-at-index/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [decoded-string-at-index](https://leetcode.cn/problems/decoded-string-at-index/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"leet2code3\"\\n10', '\"ha22\"\\n5', '\"a2345678999999999999999\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        str_len = 0\n",
    "\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                str_len *= int(c)\n",
    "            else:\n",
    "                str_len += 1\n",
    "        \n",
    "        for c in reversed(s):\n",
    "            k %= str_len\n",
    "            \n",
    "            if k == 0 and c.isalpha():\n",
    "                return c\n",
    "            \n",
    "            if c.isdigit():\n",
    "                str_len //= int(c)\n",
    "            else:\n",
    "                str_len -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        lst, n = [\"\"], 0\n",
    "        for c in s:\n",
    "            if c.isalpha():\n",
    "                if type(lst[-1]) == str: lst[-1] += c\n",
    "                else: lst.append(c)\n",
    "                n += 1\n",
    "                #if n == k: return c\n",
    "            else:\n",
    "                lst.append(x := int(c))\n",
    "                n *= x\n",
    "                if n >= k: break\n",
    "            #print(lst, n)\n",
    "        for v in lst[::-1]:\n",
    "            if type(v) == int: \n",
    "                n //= v\n",
    "                k %= n\n",
    "            else:\n",
    "                if k == 0: return v[-1]\n",
    "                if n - k < (x := len(v)): return v[::-1][n - k]\n",
    "                n -= x\n",
    "            #print(lst, v, n, k)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        '''\n",
    "        s_, n = \"\", 0\n",
    "        for c in s:\n",
    "            if c.isalpha(): \n",
    "                s_ += c\n",
    "                n += 1\n",
    "            elif c.isdigit(): \n",
    "                if n * (x := int(c)) >= k:\n",
    "                    return s_[k % n - 1]\n",
    "                else:\n",
    "                    s_ *= x\n",
    "                    n *= x\n",
    "            #print(s_, n)\n",
    "            #if n >= k: \n",
    "            #    return s_[k - 1]\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size: int = 0\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "        for c in reversed(s):\n",
    "            k %= size\n",
    "            if k == 0 and c.isalpha():\n",
    "                return c\n",
    "            if c.isdigit():\n",
    "                size //= int(c)\n",
    "            else:\n",
    "                size -= 1\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        n=len(s)\n",
    "        size=0\n",
    "        for i in range(n):\n",
    "            if s[i].isdigit():\n",
    "                size*=int(s[i])\n",
    "            else:\n",
    "                size+=1\n",
    "        for c in reversed(s):\n",
    "            k%=size\n",
    "            if k==0 and c.isalpha():\n",
    "                return c\n",
    "            if c.isdigit():\n",
    "                size=size//int(c)\n",
    "            else:\n",
    "                size-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size = 0\n",
    "        for ch in s:\n",
    "            if ch.isdigit():\n",
    "                size *= int(ch)\n",
    "            else:\n",
    "                size += 1\n",
    "        for c in s[::-1]:\n",
    "            k %= size\n",
    "            if k == 0 and c.isalpha():\n",
    "                return c\n",
    "            if c.isdigit():\n",
    "                size //= int(c)\n",
    "            else:\n",
    "                size -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        cur = 0\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                pre = cur\n",
    "                cur *= int(c) \n",
    "                if cur >= k:\n",
    "                    return self.decodeAtIndex(s, (k - 1) % pre + 1)\n",
    "            else:\n",
    "                cur += 1\n",
    "                if cur == k:\n",
    "                    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        cnt = 0\n",
    "        action = []\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                cnt *= int(c)\n",
    "                action.append([int(c), action[-1][1]])\n",
    "            else:\n",
    "                action.append([1, c])\n",
    "                cnt += 1\n",
    "            if cnt >= k:\n",
    "                break\n",
    "        while action:\n",
    "            a, c = action.pop()\n",
    "            if k % cnt == 0:\n",
    "                return c\n",
    "            if a == 1:\n",
    "                cnt -= 1\n",
    "            else:\n",
    "                cnt //= a\n",
    "                k %= cnt\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c.isalpha():\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt *= int(c)\n",
    "        \n",
    "        for c in reversed(s):\n",
    "            k %= cnt\n",
    "            if k == 0 and c.isalpha():\n",
    "                return c \n",
    "            \n",
    "            if c.isdigit():\n",
    "                cnt //= int(c)\n",
    "            else: \n",
    "                cnt -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        retVal = \"\"\n",
    "\n",
    "        size = 0\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "\n",
    "        for c in reversed(s):\n",
    "            k %= size\n",
    "            if k == 0 and c.isalpha():\n",
    "                retVal = c\n",
    "                break\n",
    "\n",
    "            if c.isdigit():\n",
    "                size /= int(c)\n",
    "            else:\n",
    "                size -= 1\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def decodeAtIndex(self, S, K):\n",
    "        size = 0\n",
    "        # Find size = length of decoded string\n",
    "        for c in S:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "\n",
    "        for c in reversed(S):\n",
    "            K %= size\n",
    "            if K == 0 and c.isalpha():\n",
    "                return c\n",
    "\n",
    "            if c.isdigit():\n",
    "                size /= int(c)\n",
    "            else:\n",
    "                size -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        lst, n = [\"\"], 0\n",
    "        for c in s:\n",
    "            if c.isalpha():\n",
    "                if type(lst[-1]) == str: lst[-1] += c\n",
    "                else: lst.append(c)\n",
    "                n += 1\n",
    "            else:\n",
    "                lst.append(int(c))\n",
    "                n *= int(c)\n",
    "                if n >= k: break\n",
    "        for v in lst[::-1]:\n",
    "            if type(v) == int: \n",
    "                n //= v\n",
    "                k %= n\n",
    "            else:\n",
    "                if k == 0: return v[-1]\n",
    "                if n - k < (x := len(v)): return v[::-1][n - k]\n",
    "                n -= x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        n = 0\n",
    "        for c in s:\n",
    "            if c.islower(): n += 1\n",
    "            if c.isdigit(): n *= int(c)\n",
    "        for c in s[::-1]:\n",
    "            if c.islower() and n == k: return c\n",
    "            if c.islower(): n -= 1\n",
    "            if c.isdigit(): n //= int(c)\n",
    "            if c.isdigit() and n < k: k = n if k % n == 0 else k % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        curr = 0\n",
    "        for c in s:\n",
    "            pre = curr\n",
    "            if c.isalpha():\n",
    "                curr += 1\n",
    "                if curr == k:\n",
    "                    return c\n",
    "            else:\n",
    "                curr *= int(c)\n",
    "                if curr >= k:\n",
    "                    return self.decodeAtIndex(s, (k-1) % pre + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        length = 0\n",
    "        preLength = 0\n",
    "        for i in range(len(s)):\n",
    "            if '0'<=s[i]<='9':\n",
    "                length = preLength * int(s[i])\n",
    "                if length >= k:\n",
    "                    return self.decodeAtIndex(s[:i], (k - 1) % preLength + 1)                   \n",
    "                preLength = length  \n",
    "            else:\n",
    "                preLength += 1\n",
    "                if preLength == k:\n",
    "                    return s[i]\n",
    "        return ''                                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size = 0\n",
    "        # Find size = length of decoded string\n",
    "        S =s\n",
    "        K =k\n",
    "        for c in S:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "\n",
    "        for c in reversed(S):\n",
    "            K = round(K % size,0)\n",
    "            k %= size\n",
    "\n",
    "            print(K,k,size)\n",
    "            if K == 0 and c.isalpha():\n",
    "                return c\n",
    "\n",
    "            if c.isdigit():\n",
    "                size = size // int(c)\n",
    "            else:\n",
    "                size -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def decodeAtIndex(self, S, K):\n",
    "        size = 0\n",
    "        # Find size = length of decoded string\n",
    "        for c in S:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "\n",
    "        for c in reversed(S):\n",
    "            K %= size\n",
    "            if K == 0 and c.isalpha():\n",
    "                return c\n",
    "\n",
    "            if c.isdigit():\n",
    "                size /= int(c)\n",
    "            else:\n",
    "                size -= 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, S: str, k: int) -> str:\n",
    "        loop = []  # loop[i] == [l, s, n]  表示前面的长度为l的字符串，接一个字符串s，一共翻n倍，前长度为l的字符串在loop下一项中表示\n",
    "        curs = ''\n",
    "        curl = 0\n",
    "        for x in S:\n",
    "            if x.isalpha():\n",
    "                curs += x\n",
    "            else:\n",
    "                x = int(x)\n",
    "                loop.insert(0, [curl, curs, x])\n",
    "                curl = (curl + len(curs)) * x\n",
    "                curs = ''\n",
    "        if len(loop) == 0:\n",
    "            return S[k - 1]\n",
    "        # k -= 1\n",
    "        for l, s, n in loop:\n",
    "            single = l + len(s)  # 单个周期长度\n",
    "            pos = (k - 1) % single\n",
    "            k %= single\n",
    "            if pos >= l:\n",
    "                return s[pos - l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size = 0\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "        for c in reversed(s):\n",
    "            k %= size\n",
    "            if k == 0 and c.isalpha():\n",
    "                return c\n",
    "            if c.isdigit():\n",
    "                size /= int(c)\n",
    "            else:\n",
    "                size -= 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        length_count = 0\n",
    "        for i in s:\n",
    "            if i.isalpha():\n",
    "                length_count += 1\n",
    "            else:\n",
    "                length_count *= int(i)\n",
    "        for i in reversed(s):\n",
    "            k %= length_count\n",
    "            if k == 0 and i.isalpha():\n",
    "                return i\n",
    "\n",
    "            if i.isdigit():\n",
    "                length_count //= int(i)\n",
    "            else:\n",
    "                length_count -= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        count = [\"\"]\n",
    "        n = 0\n",
    "        for i in s:\n",
    "            if i.isalpha() == True:\n",
    "                if type(count[-1]) == str:\n",
    "                    count[-1] += i\n",
    "                else:\n",
    "                    count.append(i)\n",
    "                n += 1\n",
    "            else:\n",
    "                count.append(int(i))\n",
    "                n *= int(i)\n",
    "                if n>=k:\n",
    "                    break\n",
    "        for v in count[::-1]:\n",
    "            if type(v)==int:\n",
    "                n = n//v\n",
    "                k = k%n\n",
    "            else:\n",
    "                if k == 0:\n",
    "                    return v[-1]\n",
    "                if n-k<len(v):\n",
    "                    return v[::-1][n-k]\n",
    "                n -= len(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        cur = 0\n",
    "        for c in s:\n",
    "            pre = cur\n",
    "            if c.isdigit():\n",
    "                cur *= int(c)\n",
    "                if cur >= k:\n",
    "                    # 当第k个字母已出现在解码字符串中，调用递归缩小范围，逐步进行计算\n",
    "                    return self.decodeAtIndex(s, (k-1) % pre + 1)\n",
    "            else:\n",
    "                cur += 1\n",
    "                if cur == k:\n",
    "                    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        n = 0\n",
    "        for ch in s:\n",
    "            if ch.isalpha():\n",
    "                n += 1\n",
    "            else:\n",
    "                n *= int(ch)\n",
    "        \n",
    "        for ch in s[::-1]:\n",
    "            k %= n\n",
    "            if k == 0 and ch.isalpha():\n",
    "                return ch\n",
    "            if ch.isalpha():\n",
    "                n -= 1\n",
    "            else:\n",
    "                n /= int(ch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size = 0\n",
    "        for ch in s:\n",
    "            if ch.isdigit():\n",
    "                size *= int(ch)\n",
    "            else:\n",
    "                size += 1\n",
    "        for ch in s[::-1]:\n",
    "            k %= size\n",
    "            if k == 0 and ch.isalpha():\n",
    "                return ch\n",
    "            if ch.isdigit():\n",
    "                size //= int(ch)\n",
    "            else:\n",
    "                size -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        vals, cur, tmp, cnts, total = [], 0, [], [], 0\n",
    "        for l in s:\n",
    "            if l.isdigit():\n",
    "                vals.append(tmp)\n",
    "                v1 = len(tmp)\n",
    "                cnts.append([cur, v1])\n",
    "                cur = (cur + v1) * int(l)\n",
    "                total *= int(l)\n",
    "                tmp = []\n",
    "                if cur >= k: break\n",
    "            else:\n",
    "                total += 1\n",
    "                if total == k: return l\n",
    "                tmp.append(l)\n",
    "        n = len(cnts)\n",
    "        k -= 1\n",
    "        # return cnts\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt, rem = cnts[i]\n",
    "            k %= (cnt + rem)\n",
    "            if k >= cnt: return vals[i][k - cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        while True:\n",
    "            l = 0\n",
    "            for i, x in enumerate(s):\n",
    "                if x.isalpha():\n",
    "                    l += 1\n",
    "                    if l == k:\n",
    "                        return s[i]\n",
    "                else:\n",
    "                    if l * int(x) >= k:\n",
    "                        k = (k - 1) % l + 1\n",
    "                        break\n",
    "                    else:\n",
    "                        l *= int(x)\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "#         stack = []\n",
    "#         for ch in s:\n",
    "#             if ch.isalpha():\n",
    "#                 stack.append(ch)\n",
    "#             else:\n",
    "#                 stack += stack * (int(ch) -1)\n",
    "#             if len(stack) >= k:\n",
    "#                 return stack[k-1]\n",
    "#         # memory issue when k is super large s = \"y959q969u3hb22odq595\", k =222280369\n",
    "#         return stack[k-1] \n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size  = 0\n",
    "\n",
    "        # Calculate the total length of the decoded string\n",
    "        for ch in s:\n",
    "            if ch.isdigit():\n",
    "                size *= int(ch)\n",
    "            else:\n",
    "                size += 1\n",
    "\n",
    "        # Traverse the string in reverse to find the character at index k\n",
    "        for ch in reversed(s):\n",
    "            k %= size  # Reduce index based on the length\n",
    "\n",
    "            # Check if the current character is the answer\n",
    "            if k == 0 and ch.isalpha():\n",
    "                return ch\n",
    "\n",
    "            # Update the length based on the current character\n",
    "            if ch.isdigit():\n",
    "                size //= int(ch)\n",
    "            else:\n",
    "                size -= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        vals, cur, tmp, cnts, total = [], 0, [], [], 0\n",
    "        for l in s:\n",
    "            if l.isdigit():\n",
    "                vals.append(tmp)\n",
    "                v1 = len(tmp)\n",
    "                cnts.append([cur, v1])\n",
    "                cur = (cur + v1) * int(l)\n",
    "                total *= int(l)\n",
    "                tmp = []\n",
    "                if cur >= k: break\n",
    "            else:\n",
    "                total += 1\n",
    "                if total == k: return l\n",
    "                tmp.append(l)\n",
    "        n = len(cnts)\n",
    "        k -= 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt, rem = cnts[i]\n",
    "            k %= (cnt + rem)\n",
    "            if k >= cnt: return vals[i][k - cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "#         stack = []\n",
    "#         for ch in s:\n",
    "#             if ch.isalpha():\n",
    "#                 stack.append(ch)\n",
    "#             else:\n",
    "#                 stack += stack * (int(ch) -1)\n",
    "#             if len(stack) >= k:\n",
    "#                 return stack[k-1]\n",
    "#         # memory issue when k is super large s = \"y959q969u3hb22odq595\", k =222280369\n",
    "#         return stack[k-1] \n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "\n",
    "        for c in s[::-1]:\n",
    "            if c.isdigit():\n",
    "                size //= int(c)\n",
    "                k %= size\n",
    "            else:\n",
    "                if k % size == 0:\n",
    "                    return c\n",
    "                size -= 1\n",
    "\n",
    "# string is read one character at a time. 22 is 2.. 2 not 22\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        lst, n = [\"\"], 0\n",
    "        for c in s:\n",
    "            if c.isalpha():\n",
    "                if type(lst[-1]) == str: lst[-1] += c\n",
    "                else: lst.append(c)\n",
    "                n += 1\n",
    "            else:\n",
    "                lst.append(x := int(c))\n",
    "                n *= x\n",
    "                if n >= k: break\n",
    "        for v in lst[::-1]:\n",
    "            if type(v) == int: \n",
    "                n //= v\n",
    "                k %= n\n",
    "            else:\n",
    "                if k == 0: return v[-1]\n",
    "                if n - k < (x := len(v)): return v[::-1][n - k]\n",
    "                n -= x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str: \n",
    "        ind=0\n",
    "        dig={\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\"}\n",
    "        for w in s:\n",
    "            if w in dig:\n",
    "                ind *=int(w)\n",
    "            else:\n",
    "                ind +=1\n",
    "        for w in reversed(s):\n",
    "            k %=ind\n",
    "            if k==0 and w.isalpha():\n",
    "                return w\n",
    "            if w in dig:\n",
    "                ind //=int(w)\n",
    "            else:\n",
    "                ind -=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        count = [\"\"]\n",
    "        n = 0\n",
    "        for i in s:\n",
    "            if i.isalpha() == True:\n",
    "                if type(count[-1]) == str:\n",
    "                    count[-1] += i\n",
    "                else:\n",
    "                    count.append(i)\n",
    "                n += 1\n",
    "            else:\n",
    "                count.append(int(i))\n",
    "                n *= int(i)\n",
    "                if n>=k:\n",
    "                    break\n",
    "        for v in count[::-1]:\n",
    "            if type(v)==int:\n",
    "                n = n//v\n",
    "                k = k%n\n",
    "            else:\n",
    "                if k == 0:\n",
    "                    return v[-1]\n",
    "                if n-k<len(v):\n",
    "                    return v[::-1][n-k]\n",
    "                n -= len(v)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\r\n",
    "        n = len(s) \r\n",
    "        cur = 0 \r\n",
    "        for i in range(n):\r\n",
    "            if s[i].isdigit():\r\n",
    "                d = int(s[i])\r\n",
    "                if cur * d >= k:\r\n",
    "                    return self.decodeAtIndex(s[:i], k % cur + cur * int(k % cur == 0))\r\n",
    "                cur *= d \r\n",
    "            else:\r\n",
    "                if cur + 1 == k:\r\n",
    "                    return s[i]\r\n",
    "                cur += 1 \r\n",
    "        return s[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        i=cnt = 0\n",
    "        x = []\n",
    "        c = ''\n",
    "        ret = ''\n",
    "        while i < len(s) and cnt < k:\n",
    "            if s[i].isdigit():\n",
    "                cnt *= int(s[i])\n",
    "                if s[i - 1].isdigit():\n",
    "                    x[-1][0] = cnt\n",
    "                else:\n",
    "                    x.append([cnt, len(c) - 1])\n",
    "\n",
    "            else:\n",
    "                c += s[i]\n",
    "                cnt += 1\n",
    "                x.append([cnt, len(c) - 1])\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        while x:\n",
    "            t = x.pop()\n",
    "            k %= t[0]\n",
    "            if k == 0:\n",
    "                ret = c[t[1]]\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\r\n",
    "        n = len(s) \r\n",
    "        cur = 0 \r\n",
    "        for i in range(n):\r\n",
    "            if s[i].isnumeric():\r\n",
    "                d = int(s[i])\r\n",
    "                if cur * d >= k:\r\n",
    "                    return self.decodeAtIndex(s[:i], k % cur + cur * int(k % cur == 0))\r\n",
    "                cur *= d \r\n",
    "            else:\r\n",
    "                if cur + 1 == k:\r\n",
    "                    return s[i]\r\n",
    "                cur += 1 \r\n",
    "        return s[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        cur = 0\n",
    "        for c in s:\n",
    "            pre = cur\n",
    "            if c.isdigit():\n",
    "                cur *= int(c)\n",
    "                if cur >= k:\n",
    "                    return self.decodeAtIndex(s, (k-1) % pre + 1)\n",
    "            else:\n",
    "                cur += 1\n",
    "                if cur == k:\n",
    "                    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size = 0\n",
    "        # Find size = length of decoded string\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "\n",
    "        for c in reversed(s):\n",
    "            k %= size\n",
    "            if k == 0 and c.isalpha():\n",
    "                return c\n",
    "\n",
    "            if c.isdigit():\n",
    "                size /= int(c)\n",
    "            else:\n",
    "                size -= 1\n",
    "\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        cur = 0\n",
    "        for c in s:\n",
    "            pre = cur\n",
    "            if c.isdigit():\n",
    "                cur *= int(c)\n",
    "                if cur >= k:\n",
    "                    return self.decodeAtIndex(s, (k - 1) % pre + 1)\n",
    "            else:\n",
    "                cur += 1\n",
    "                if cur == k:\n",
    "                    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "#         stack = []\n",
    "#         for ch in s:\n",
    "#             if ch.isalpha():\n",
    "#                 stack.append(ch)\n",
    "#             else:\n",
    "#                 stack += stack * (int(ch) -1)\n",
    "#             if len(stack) >= k:\n",
    "#                 return stack[k-1]\n",
    "#         # memory issue when k is super large s = \"y959q969u3hb22odq595\", k =222280369\n",
    "#         return stack[k-1] \n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        total_length = 0\n",
    "\n",
    "        # Calculate the total length of the decoded string\n",
    "        for char in s:\n",
    "            if char.isdigit():\n",
    "                total_length *= int(char)\n",
    "            else:\n",
    "                total_length += 1\n",
    "\n",
    "        # Traverse the string in reverse to find the character at index k\n",
    "        for char in reversed(s):\n",
    "            k %= total_length  # Reduce index based on the length\n",
    "\n",
    "            # Check if the current character is the answer\n",
    "            if k == 0 and char.isalpha():\n",
    "                return char\n",
    "\n",
    "            # Update the length based on the current character\n",
    "            if char.isdigit():\n",
    "                total_length //= int(char)\n",
    "            else:\n",
    "                total_length -= 1\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "#         # step 1: 先求出最后解码字符串的长度\n",
    "#         size = 0\n",
    "#         for i, c in enumerate(s):\n",
    "#             if c.isdigit():\n",
    "#                 size *= int(c)\n",
    "#             else:\n",
    "#                 size += 1\n",
    "#             # 个优化，如果在中间长度已经大于k了，就结束在这里，开始向前做。\n",
    "#             if k <= size:\n",
    "#                 break\n",
    "#         # step 2: 从后向前遍历，遇到数字，长度除这个数，遇到字母长度减一，并且每次用k对size取模。\n",
    "#         for c in s[i::-1]:\n",
    "#             if c.isdigit():\n",
    "#                 size /= int(c)\n",
    "#                 k %= size\n",
    "#             else:\n",
    "#                 if k % size == 0:\n",
    "#                     return c\n",
    "#                 size -= 1\n",
    "\n",
    "\n",
    "# 先求出最后解码字符串的长度，从后向前遍历，遇到数字，长度除这个数，遇到字母长度减一，并且每次用k对size取模。一个优化，如果在中间长度已经大于k了，就结束在这里，开始向前做。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        # size代表将要解码的字符串的长度\n",
    "        size = 0\n",
    "        # 遍历字符串，如果为数字，重复size次，如果为字母，字符串长度加 1\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "        # 反向遍历字符串\n",
    "        for c in reversed(s):\n",
    "            # 尝试缩小 k 的值\n",
    "            k %= size  # type: ignore\n",
    "            # 如果 k / size 可以整除，并且当前字母为字母，返回当前字母\n",
    "            # 因为当字符串的长度为某个长度为size的字符重复若干次时\n",
    "            # 索引 k 位的字符就是索引 k % size 位的字符\n",
    "            if k == 0 and c.isalpha():\n",
    "                return c\n",
    "            # 如果当前遇到的是数字，逆运算求得重复之前的字符串的长度\n",
    "            if c.isdigit():\n",
    "                size /= int(c)\n",
    "            # 如果遇到的是字母，字符串长度减 1\n",
    "            else:\n",
    "                size -= 1\n",
    "        # 如果没有找到，返回空字符串\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size = 0\n",
    "    \n",
    "    # Calculate the size of the decoded string\n",
    "        for char in s:\n",
    "            if char.isdigit():\n",
    "                size *= int(char)\n",
    "            else:\n",
    "                size += 1\n",
    "        \n",
    "        # Work backwards to find the k-th character\n",
    "        for char in reversed(s):\n",
    "            k %= size\n",
    "            if k == 0 and char.isalpha():\n",
    "                return char\n",
    "\n",
    "            if char.isdigit():\n",
    "                size /= int(char)\n",
    "            else:\n",
    "                size -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            if s[i].isnumeric():\n",
    "                d = int(s[i])\n",
    "                if cur * d >= k:\n",
    "                    return self.decodeAtIndex(s[:i], k % cur + cur*int(k%cur==0))\n",
    "                cur *= d\n",
    "            else:\n",
    "                if cur + 1 == k:\n",
    "                    return s[i]\n",
    "                cur += 1\n",
    "        return s[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        length = 0\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch.isdigit():\n",
    "                length *= int(ch)\n",
    "            else:\n",
    "                length += 1\n",
    "            stack.append(length)\n",
    "            if length >= k:\n",
    "                break\n",
    "        for i in range(len(stack)-1, -1, -1):\n",
    "            length = stack[i]    # length 必定大于等于 k\n",
    "            if s[i].isdigit():\n",
    "                k %= stack[i-1]\n",
    "                if not k:\n",
    "                    k += stack[i-1]\n",
    "            else:\n",
    "                if k == 1:\n",
    "                    return s[0]\n",
    "                if k == length:\n",
    "                    return s[i]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        stack = []\n",
    "        add = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i].isdigit():\n",
    "                add *= int(s[i])\n",
    "            else:\n",
    "                add += 1\n",
    "            stack.append(s[i])\n",
    "        while stack:\n",
    "            k = k % add\n",
    "            if k == 0 and stack[-1].isalpha():\n",
    "                return stack[-1]\n",
    "            \n",
    "            if stack[-1].isdigit():\n",
    "                add = add // int(stack.pop())\n",
    "            else:\n",
    "                add -= 1\n",
    "                stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\r\n",
    "        size=0\r\n",
    "        idx=-1\r\n",
    "        for i,c in enumerate(s):\r\n",
    "            if c.isalpha():\r\n",
    "                size+=1\r\n",
    "            else:\r\n",
    "                size*=int(c)\r\n",
    "            if size>=k:\r\n",
    "                idx=i\r\n",
    "                break\r\n",
    "        for i in range(idx,-1,-1):\r\n",
    "            k%=size\r\n",
    "            if k==0 and s[i].isalpha():\r\n",
    "                return s[i]\r\n",
    "            if s[i].isalpha():\r\n",
    "                size-=1\r\n",
    "            else:\r\n",
    "                size//=int(s[i])\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        def is_num(x: str):\n",
    "            if 0 <= ord(x) - ord('0') <= 9:\n",
    "                return True\n",
    "\n",
    "        cur = 0\n",
    "        cnt = 0\n",
    "        for x in s:\n",
    "            if is_num(x):\n",
    "                cnt *= int(x)\n",
    "                if cnt >= k:\n",
    "                    res = k % cur\n",
    "                    return self.decodeAtIndex(s, res if res > 0 else cur)\n",
    "                cur *= int(x)\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return x\n",
    "                cur += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=880 lang=python3\n",
    "#\n",
    "# [880] 索引处的解码字符串\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution:\n",
    "    def decodeAtIndex1(self, s: str, k: int) -> str:\n",
    "        f = [(0, 1, 0, \"\")]\n",
    "        cnt = 0\n",
    "        word = \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            if c.isalpha():\n",
    "                cnt += 1\n",
    "                word += c\n",
    "            else:\n",
    "                f.append(((cnt + f[-1][0]) * int(s[i]), int(s[i]), cnt, word))\n",
    "                cnt = 0\n",
    "                word = \"\"\n",
    "        l, r = 0, len(f) - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if f[mid][0] >= k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        if f[l][0] < k:\n",
    "            return word[k - f[l][0] - 1]\n",
    "        while True:\n",
    "            block = f[l][0] // f[l][1]\n",
    "            d = k\n",
    "            if k > block:\n",
    "                d = k % block\n",
    "                if d == 0:\n",
    "                    d = block\n",
    "            pre = block - f[l][2]\n",
    "            if d > pre:\n",
    "                return f[l][3][d - pre - 1]\n",
    "            else:\n",
    "                l -= 1\n",
    "                k = d\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size = 0\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "        for c in reversed(s):\n",
    "            k %= size\n",
    "            if k == 0 and c.isalpha():\n",
    "                return c\n",
    "            if c.isdigit():\n",
    "                size //= int(c)\n",
    "            else:\n",
    "                size -= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        total_len = 0\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                total_len *= int(c)\n",
    "            else:\n",
    "                total_len += 1\n",
    "        # in reverse order\n",
    "        for c in reversed(s):\n",
    "            if c.isdigit():\n",
    "                total_len /= int(c)\n",
    "                k %= total_len\n",
    "            else:\n",
    "                if k == 0 or k == total_len:\n",
    "                    return c\n",
    "                total_len -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        length = 0\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                length *= int(c)\n",
    "            else:\n",
    "                length += 1\n",
    "        for c in reversed(s):\n",
    "            k %= length\n",
    "            if k == 0 and c.islower():\n",
    "                return c\n",
    "            if c.isdigit():\n",
    "                length //= int(c)\n",
    "            else:\n",
    "                length -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(1000000)\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        def is_num(x: str):\n",
    "            if 0 <= ord(x) - ord('0') <= 9:\n",
    "                return True\n",
    "\n",
    "        cur = 0\n",
    "        cnt = 0\n",
    "        for x in s:\n",
    "            if is_num(x):\n",
    "                cnt *= int(x)\n",
    "                if cnt >= k:\n",
    "                    res = k % cur\n",
    "                    return self.decodeAtIndex(s, res if res > 0 else cur)\n",
    "                cur *= int(x)\n",
    "            else:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return x\n",
    "                cur += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        length = 0\n",
    "        preLength = 0\n",
    "        sstack = []\n",
    "        cstack = []\n",
    "        print(s, k)\n",
    "        for i in range(len(s)):\n",
    "            if '0' <= s[i] <= '9':\n",
    "                length = preLength * int(s[i])\n",
    "                if length >= k:\n",
    "                    return self.decodeAtIndex(s[:i], (k - 1) % preLength + 1)                   \n",
    "                preLength = length  \n",
    "            else:\n",
    "                preLength += 1\n",
    "                if preLength == k:\n",
    "                    return s[i]\n",
    "        return ''                                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def decodeAtIndex(self, s , k ) :\n",
    "    l = 0\n",
    "    for ch in s:\n",
    "      if ch <= '9' and ch >= '0':\n",
    "        l = l * int(ch)\n",
    "      else:\n",
    "        l += 1\n",
    "      \n",
    "    for ch in reversed(s):\n",
    "      k %= l\n",
    "      if k == 0 and ch.isalpha():\n",
    "        return ch\n",
    "      \n",
    "      if ch.isdigit():\n",
    "        l = l // int(ch)\n",
    "      else:\n",
    "        l -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\r\n",
    "        size = 0 # length of decoded string\r\n",
    "        for ch in s:\r\n",
    "            if ch.isdigit():\r\n",
    "                size *= int(ch)\r\n",
    "            else:\r\n",
    "                size += 1\r\n",
    "        for ch in reversed(s): # 由後往前，縮減長度\r\n",
    "            k %= size\r\n",
    "            if k == 0 and ch.isalpha():\r\n",
    "                return ch\r\n",
    "            if ch.isdigit(): # 前面的字串重複int(ch)次，所以長度可以縮減int(ch)倍\r\n",
    "                size //= int(ch)\r\n",
    "            else:\r\n",
    "                size -= 1\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeAtIndex(self, s: str, k: int) -> str:\n",
    "        size = 0\n",
    "        for c in s:\n",
    "            if c.isdigit():\n",
    "                size *= int(c)\n",
    "            else:\n",
    "                size += 1\n",
    "        for c in reversed(s):\n",
    "            k %= size\n",
    "            if k == 0 and c.isalpha():\n",
    "                return c\n",
    "            if c.isdigit():\n",
    "                size /= int(c)\n",
    "            else:\n",
    "                size -= 1\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
